Big Sky

Go でスライスに挿入する例として Go の Wiki に以下の物が記載されている。

作ろうしているツールで、
Goのスライスのinsertをする必要があって、
スライスの動きを理解するために、自分で実装したあとに、Goの公式Wikiを見て頭いいなと思ったhttps://t.co/vmonuxbjOl
a = append(a[:i], append([]T{x}, a[i:]...)...)
— ゴリラ@バナナバナナバナナバナナバナナバナナバナナバナナバナナバナナバナナバナナバナナバナナバナナ (@gorilla0513) April 4, 2020

しかしこのコードは、挿入されるスライスから部分スライスを取り出し、そこに挿入するスライスを append に割り当てる為に展開し、さらに残りの部分スライスも append に割り当てる展開を行っている。なので実装コードとしては短いが、実際に実行されるオペレーションコードが冗長になる。また、スライスの伸長はおよそ2倍ずつ増える。なので例えば 5000 個のスライスに 1000 個のアイテムを挿入すると、キャパシティはおよそ 12000 近くになる。Go ではこういったスライスの操作も、基本的には自身で make によりメモリを確保し、ループで値を割り当てるのが良い(面倒かもしれないがその方がメモリも節約され速い)とされている。

以下、ベンチマークを取ってみる。


package main_test



import (

    "reflect"

    "testing"

)



type T int



func BenchmarkAppend(b *testing.B) {

    b.ResetTimer()



    input := make([]int, 5000)

    for i := 0; i < 5000; i++ {

        input[i] = i

    }

    insert := make([]int, 1000)

    for i := 0; i < 1000; i++ {

        insert[i] = i

    }

    expected := make([]int, 6000)

    for i := 0; i < 6000; i++ {

        if i < 1000 {

            expected[i] = i

        } else if i < 2000 {

            expected[i] = i - 1000

        } else {

            expected[i] = i - 1000

        }

    }

    n := 1000

    var output []int



    b.ResetTimer()

    for i := 0; i < b.N; i++ {

        output = append(input[:n], append(insert, input[n:]...)...)

    }

    b.StopTimer()

    if !reflect.DeepEqual(output, expected) {

        b.Fatal("bad insertion")

    }

}



func BenchmarkNormal(b *testing.B) {

    input := make([]int, 5000)

    for i := 0; i < 5000; i++ {

        input[i] = i

    }

    insert := make([]int, 1000)

    for i := 0; i < 1000; i++ {

        insert[i] = i

    }

    expected := make([]int, 6000)

    for i := 0; i < 6000; i++ {

        if i < 1000 {

            expected[i] = i

        } else if i < 2000 {

            expected[i] = i - 1000

        } else {

            expected[i] = i - 1000

        }

    }

    n := 1000

    var output []int



    b.ResetTimer()

    for i := 0; i < b.N; i++ {

        output = make([]int, len(input)+len(insert))

        for l := 0; l < n; l++ {

            output[l] = input[l]

        }

        for l := 0; l < len(insert); l++ {

            output[l+n] = insert[l]

        }

        for l := n; l < len(input); l++ {

            output[l+len(insert)] = input[l]

        }

    }

    b.StopTimer()

    if !reflect.DeepEqual(output, expected) {

        b.Fatal("bad insertion")

    }

}



func BenchmarkCopy(b *testing.B) {

    input := make([]int, 5000)

    for i := 0; i < 5000; i++ {

        input[i] = i

    }

    insert := make([]int, 1000)

    for i := 0; i < 1000; i++ {

        insert[i] = i

    }

    expected := make([]int, 6000)

    for i := 0; i < 6000; i++ {

        if i < 1000 {

            expected[i] = i

        } else if i < 2000 {

            expected[i] = i - 1000

        } else {

            expected[i] = i - 1000

        }

    }

    n := 1000

    var output []int



    b.ResetTimer()

    for i := 0; i < b.N; i++ {

        output = make([]int, len(input)+len(insert))

        copy(output, input[:n])

        copy(output[n:], insert)

        copy(output[n+len(insert):], input[n:])

    }

    b.StopTimer()

    if !reflect.DeepEqual(output, expected) {

        b.Fatal("bad insertion")

    }

}


BenchmarkAppend-8          42700             26185 ns/op

BenchmarkNormal-8          70170             18005 ns/op

BenchmarkCopy-8            90902             15787 ns/op

Wiki に載っているコードは、手動でスライスを挿入するコードの1.5～2倍遅い。copy を使うともう少し速い。